package com.xyhuo.leetcode.january;

import java.util.ArrayList;
import java.util.List;

/**
 * 被围绕的区域
 * https://leetcode.cn/problems/surrounded-regions/
 *
 * @time 2024/1/12
 */
public class Solve {

//    public static void main(String[] args) {
//        Solve solve = new Solve();
////        char[][] board = {{'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}};
////        char[][] board = {
////                {'X', 'O', 'X'},
////                {'X', 'O', 'X'},
////                {'X', 'O', 'X'}};
////        char[][] board = {
////                {'X', 'O', 'X', 'O', 'X'},
////                {'O', 'X', 'O', 'O', 'O'},
////                {'X', 'X', 'O', 'X', 'O'}};
//
//        char[][] board = {{'O', 'O', 'O', 'O', 'X', 'X'}, {'O', 'O', 'O', 'O', 'O', 'O'}, {'O', 'X', 'O', 'X', 'O', 'O'}, {'O', 'X', 'O', 'O', 'X', 'O'}, {'O', 'X', 'O', 'X', 'O', 'O'}, {'O', 'X', 'O', 'O', 'O', 'O'}};
//        solve.solve(board);
//    }

    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'X') {
                    continue;
                }
                List<int[]> list = new ArrayList<>();
                int[][] already = new int[m][n];
                boolean find = search(board, i, j, already, list);
                if (find) {
                    for (int k = 0; k < list.size(); k++) {
                        int[] indexItem = list.get(k);
                        board[indexItem[0]][indexItem[1]] = 'X';
                    }
                }
            }
        }
    }

    private boolean search(char[][] board, int i, int j, int[][] already, List<int[]> list) {
        if (i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1) {
            return false;
        }
        boolean find = true;
        int[][] direct = {{i - 1, j}, {i, j - 1}, {i + 1, j}, {i, j + 1}};
        for (int k = 0; k < direct.length; k++) {
            int newI = direct[k][0], newJ = direct[k][1];
            if (find && already[newI][newJ] == 0 && board[newI][newJ] == 'O') {
                already[i][j] = 1;
                find &= search(board, newI, newJ, already, list);
            }
        }
        if (find) {
            int[] indexItem = {i, j};
            list.add(indexItem);
        }
        return find;
    }
}
